package DP.背包.每样1个;

import org.junit.Test;

/**
 * 背包 dp
 *    纯汉译瞎写
 *
 * 特：
 *     if{双int}
 *     -> 防止int na=0 可能有负数
 */
public class 背包_每样1个_dp {
    int N = 3, W = 4;
    int[] w = new int[]{2, 1, 3};
    int[] v = new int[]{4, 2, 3};
    @Test
    public void test() {
        int[][] dp = new int[N+1][W+1]; // +1 因为要表示实际123数字

        // 初 [0][] [][0] (可能其一即可)
        for (int preNum = 0; preNum < dp.length; preNum++) {
            for (int limW = 0; limW < dp[0].length; limW++) {
                dp[preNum][limW] = 0;
            }
        }

        for (int preNum = 1; preNum <= N; preNum++) {
            for (int limW = 1; limW <= W; limW++) {
                int cI = preNum - 1;
                if(limW >= w[cI]){
                    //           前-1个的最值             + 当前[v]
                    int na = dp[preNum-1][limW - w[cI]] + v[cI];
                    int buna = dp[preNum - 1][limW]; // 防止int na=0 可能有负数
                    dp[preNum][limW] = Math.max(na, buna);
                }else {
                    int buna = dp[preNum - 1][limW];
                    dp[preNum][limW] = buna;
                }
            }
        }
        System.out.println(dp[N][W]);
        return;
    }
}
